package com.lun.swordtowardoffer2.c07;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import com.lun.util.BinaryTree.TreeNode;

public class RightSignView {

	public List<Integer> rightSideView(TreeNode root){
		Queue<TreeNode> queue1 = new LinkedList<>();
		Queue<TreeNode> queue2 = new LinkedList<>();
		
		boolean queue1Flag = true;
		List<Integer> result = new ArrayList<>();
		
		Queue<TreeNode> currentQueue = null;
		
		if(root != null) {
			queue1.offer(root);
			currentQueue = queue1;
		}
		
		while(!currentQueue.isEmpty()) {
			TreeNode node = currentQueue.poll();
			
			Queue<TreeNode> nextQueue = queue1Flag ? queue2 : queue1;
			
			if(node.left != null) {
				nextQueue.offer(node.left);
			}
			
			if(node.right != null) {
				nextQueue.offer(node.right);
			}
			
			if(currentQueue.isEmpty()) {
				currentQueue = nextQueue;
				queue1Flag = !queue1Flag;
				result.add(node.val);
			}
		}
		
		return result;
	}
	
}
